qr_mumps

• <2024-04-11 Thu> qr_mumps v 3.1 released (Changelog)
• <2021-07-06 Tue> qr_mumps v 3.0.4 released (Changelog)
• <2021-06-08 Tue> qr_mumps v 3.0.3 released (Changelog)
• <2021-04-30 Fri> qr_mumps now has a Julia interface! It is available HERE. Thanks to Alexis Montoison for developing it.
• <2021-04-13 Tue> qr_mumps v 3.0.2 released (Changelog)
• <2021-02-03 Wed> qr_mumps v 3.0.1 released (Changelog)
• <2020-10-20 Tue> qr_mumps v 3.0 released (Changelog)
• <2016-06-29 Wed> qr_mumps v 2.0 released (Changelog)
• <2016-02-01 Mon> qr_mumps v 1.2 released (Changelog)

qr_mumps is a software package for the solution of sparse, linear systems on multicore computers. It implements a direct solution method based on the QR or Cholesky factorization of the input matrix. Therefore, it is suited to solving sparse least-squares problems, to computing the minimum-norm solution of sparse, underdetermined problems and to solving symmetric, positive-definite sparse linear systems. It can obviously be used for solving square unsymmetric problems in which case the stability provided by the use of orthogonal transformations comes at the cost of a higher operation count with respect to solvers based on, e.g., the LU factorization such as MUMPS. qr_mumps supports real and complex, single or double precision arithmetic. qr_mumps

As in all the sparse, direct solvers, the solution is achieved in three distinct phases:

Analysis

in this phase an analysis of the structural properties of the input matrix is performed in preparation for the numerical factorization phase. This includes computing a column permutation which reduces the amount of fill-in coefficients (i.e., nonzeroes introduced by the factorization). This step does not perform any floating-point operation and is, thus, commonly much faster than the factorization and solve (depending on the number of right-hand sides) phases.

Factorization

at this step, the actual \(QR\) or Cholesky factorization is computed. This step is the most computationally intense and, therefore, the most time consuming.

Solution

once the factorization is done, the factors can be used to compute the solution of the problem through two operations:

Solve

this operation computes the solution of the triangular system \(Rx=b\) or \(R^Tx=b\);

Apply

this operation applies the \(Q\) orthogonal matrix to a vector, i.e., \(y = Qx\) or \(y = Q^Tx\).

These three steps have to be done in order but each of them can be performed multiple times. If, for example, the problem has to be solved against multiple right-hand sides (not all available at once), the analysis and factorization can be done only once while the solution is repeated for each right-hand side. By the same token, if the coefficients of a matrix are updated but not its structure, the analysis can be performed only once for multiple factorization and solution steps.

qr_mumps is a parallel, multithreaded software based on the StarPU runtime engine (older versions based on OpenMP are still available for download) and currently runs on multicore or, more generally, shared memory multiprocessor computers; Nvidia GPUs are also supported since version 3.0. qr_mumps does not run on distributed memory (e.g. clusters) parallel computers. Parallelism is achieved through a decomposition of the workload into fine-grained computational tasks which basically correspond to the execution of a BLAS or LAPACK operation on blocks. It is strongly recommended to use sequential BLAS and LAPACK libraries and let qr_mumps have full control of the parallelism. Parallelism is achieved by dividing the workload into fine grained tasks that are arranged in a Direct Acyclic Graph (DAG). The execution of these tasks is guiged by an asynchronous and dynamic data-flow programming model which provides high efficiency and scalability.

qr_mumps is built upon the large knowledge base and know-how developed by the members of the MUMPS project. However, qr_mumps does not share any code with the MUMPS package and it is a completely independent software. qr_mumps is developed and maintained effort by the APO team of the IRIT laboratory of Toulouse and the HiePACS team at Inria Bordeaux, France.

Features:

• Supports unsymmetric, possibly rectangular problems through the \(QR\) factorization and symmetric positive-definite problems. through the Cholesky one.
• Task-based parallelism based on the StarPU runtime system
• Supports multicore systems possibly equipped with Nvidia GPUs.
• Orderings: qr_mumps supports COLAMD, Scotch and Metis fill-reducing orderings. Orderings can also be explicitly provided through the qr_mumps API.
• Memory constrained execution: the memory consumption of the parallel code can be bound by any (small) multiple of the sequential execution.
• Asynchronous interface: operations can be pipelined for additional parallelism.
• C interface: qr_mumps is written in Fortran 2008 but has a portable C interface.

The lastest qr_mumps version can be downloaded here .

Alternatively, you can get it from the gitlab repo.

qr_mumps can also be installed through Guix or Spack.

• Emmanuel Agullo (Concace, Inria Sud-Ouest)
• Alfredo Buttari (APO, CNRS-IRIT)
• Abdou Guermouche (Topal, Universite de Bordeaux)
• Florent Lopez (Ansys)

• The design of qr_mumps is deeply influenced by the countless advices from Patrick Amestoy, Jean-Yves L'Excellent and Chiara Puglisi, the developers of the MUMPS and HSL MA49 solvers.
• We are also grateful to the StarPU development team for their constant support in the use of this runtime system.
• Thanks Arnaud Legrand, Lucas Schnorr and Luka Stanisic for their feedback on performance analysis through SimGrid and StarVZ.
• qr_mumps was partially funded by the ANR SOLHAR and SOLHARIS projects.
• The development, testing and performance evaluation of qr_mumps are possible thanks to the computing resources provided by the CALMIP and PlaFRIM supercomputing centers as well as those of the GENCI consortium.
• Thanks to Alexis Montoison for developing the qr_mumps Julia interface.